/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int *path,*len;
int **ans;
int pathsize,anssize;
void backtrace(int target,int st,int *candidates,int candidatesSize)
{
    if(target<0) return; //和过大，直接返回
    if(target==0) //满足条件
    {
        int *temp=(int*)malloc(sizeof(int)*pathsize);
        for(int i=0;i<pathsize;i++) temp[i]=path[i];
        len[anssize]=pathsize;  //记录该组合的长度
        ans[anssize++]=temp; //保存一个结果
        return;
    }
    for(int i=st;i<candidatesSize;i++)
    {
        path[pathsize++]=candidates[i];
        target-=candidates[i];
        backtrace(target,i,candidates,candidatesSize); //可以重复选
        target+=candidates[i];
        pathsize--;
    }
}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    path=(int*)malloc(sizeof(int)*50);
    len=(int*)malloc(sizeof(int)*160);
    ans=(int**)malloc(sizeof(int*)*160);
    pathsize=anssize=0;
    backtrace(target,0,candidates,candidatesSize);
    *returnSize=anssize;
    *returnColumnSizes=(int*)malloc(sizeof(int)*anssize);
    for(int i=0;i<anssize;i++) (*returnColumnSizes)[i]=len[i];
    return ans;
}